package com.example.synatx.parallel;

import java.util.concurrent.RecursiveTask;

/**
 * 分支合并计算求和
 * 使用分支合并框架的最佳做法
 * 1. 对一个任务调用join方法会阻塞调用方,直到任务作出结果.因此,有必要在两个子任务的计算都开始以后再调用它.
 * 2.不应该在RecursiveTask内部使用ForkJoinPool的invoke方法.相反,你应该始终直接调用compute或fork方法,只有顺序代码才调用invoke来启动并行计算.
 * 3.对子任务调用fork方法可以把它排进ForkJoinPool.同时对左边和右边的子任务调用它似乎很自然,但是这样做的效率要比直接对一个调用compute低.这样做
 * 你可以为其中一个子任务重用同一线程,从而避免在线程池中多分配一个任务造成开销.
 * 4.调试使用分支合并框架的并行计算可能有点棘手.因为调用compute的线程并不是概念上的调用方,后者是调用fork的那个
 * 5.不应理所应当的认为在多核处理器上使用分支合并框架就比顺序计算快.
 *
 * 必须选择一个标准来决定任务是否要进一步查分还是小的已经可以顺序求值.
 *
 * 工作窃取(work stealing) 分支合并框架采用了该方法来解决线程间工作不均的情况.
 * 任务差不多平均分欧赔到ForkJoinPool中的所有线程上.每个线程都被为分配给它的任务保存一个双向链式队列.每完成一个任务,就会从队列头上取出下一个任务
 * 开始执行.这时某个线程可能已经完成了分配给它的任务,也就是它的队列已经空了,而其他线程很忙.这时这个线程并没有闲下来,而是随机选一个别的线程,从队列的尾巴
 * "偷走"一个任务.这个过程一直持续下去,知道所有的任务都执行完毕.所有的队列都被清空.
 * 工作窃取算法用于在池中的工作线程之间重新分配和平衡任务.
 */
public class ForkJoinSumCalc extends RecursiveTask<Long> {
    private final long[] numbers;
    private final int start;
    private final int end;

    public static final long THREDHOLD=10_000;

    public ForkJoinSumCalc(long[] numbers,int start,int end){
        this.numbers = numbers;
        this.start = start;
        this.end = end;
    }

    public ForkJoinSumCalc(long[] numbers){
        this(numbers,0,numbers.length);
    }

    @Override
    protected Long compute() {
        int length = end - start;
        if(length < THREDHOLD){
            return computeSequentially();
        }
        ForkJoinSumCalc leftTask = new ForkJoinSumCalc(numbers,start,start+length/2);
        leftTask.fork();
        ForkJoinSumCalc rightTask = new ForkJoinSumCalc(numbers,start+length/2,end);
        rightTask.fork();
        Long rightResult = rightTask.join();
        Long leftResult = leftTask.join();

        return rightResult+leftResult;
    }

    private long computeSequentially(){
        long sum = 0;
        for (int i = start;i<end;i++){
            sum += numbers[i];
        }
        return sum;
    }
}
